//k次取反后最大化的数组和
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;
        int sum = 0;
        for(size_t i = 0 ; i < nums.size() ; ++i)
        {
            sum += nums[i];
            pq.push(nums[i]);
        }
        while(k--)
        {
            int temp = pq.top();
            sum -= 2*temp;
            pq.pop();
            pq.push(-temp);
        }
        return sum;
    }
};

//按身高排序
class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> index(n);
        for(size_t i = 0 ; i < n ; ++i)
        {
            index[i] = i;
        }
        //对下标数组进行排序
        sort(index.begin() , index.end() , [&](int x , int y){
            return heights[x] > heights[y];
        });
        vector<string> ret;
        for(size_t i = 0 ; i < index.size() ; ++i)
        {
            ret.push_back(names[index[i]]);
        }
        return ret;
    }
};

//优势洗牌
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        unordered_map<int,vector<size_t>> hash; //nums2[i] : i
        for(size_t i = 0 ; i < n ; ++i)
        {
            hash[nums2[i]].push_back(i);
        }
        sort(nums1.begin() , nums1.end());
        sort(nums2.begin() , nums2.end());
        int left = 0 , right = n - 1 , cur1 = 0 , cur2 = 0;
        int stronger = n-1;
        vector<int> ret(n);
        for( ; cur1 < n ; ++cur1)
        {
            vector<size_t>& temp= hash[nums2[cur2]];
            if(nums1[cur1] > nums2[cur2])
            {
                //比的过就比
                ret[temp[temp.size()-1]] = nums1[cur1];
                if(temp.size() > 1) temp.pop_back();
                cur2++;
            }
            else 
            {
                //比不过去拖累掉nums2最强的
                ret[hash[nums2[stronger]][hash[nums2[stronger]].size()-1]] = nums1[cur1];
                if(hash[nums2[stronger]].size() > 1) hash[nums2[stronger]].pop_back();
                stronger++;
            }
        }
        return ret;
    }
};

//最长回文串
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> hash;
        bool isPal = false;
        int ret = 0;
        for(auto& ch : s)
        {
            hash[ch]++;
        }
        for(auto e : hash)
        {
            if(e.second % 2 != 0)
            {
                e.second--;
                isPal = true;
            }
            ret += e.second;
        }
        if(isPal == true) ret += 1;
        return ret;
    }
};